﻿#define _CRT_SECURE_NO_WARNINGS 1

#define QUESTIONS 10
#if QUESTIONS == 1 // 1 公园

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MN = 4e4 + 1;
vector<int> a[MN];
int TE, FE, S, TFE, T, F, N, M, x, y, ans = INT_MAX, RT[MN], RF[MN], RN[MN], V[MN];
// RT[i], RF[i], RN[i] 分别记录T, F, N点到i点的距离
// V[i]记录i点被访问过的次数
// 分别以T, F, N为起点进行bfs
// 枚举每个点i: 以i点为两人的集合点，则总消耗为：ans = min(ans, RT[i] * TE + RF[i] * FE + RN[i] * TFE);
// 注意先对Tm F不能全被访问到，则说明两人不能全部到达景点N，输出-1
// 枚举时需要注意V[i] != 0; 如果V[i] == 0说明i点孤立与T, F, N点
void bfs(int start, int times, int arr[])
{
	queue<int> q;
	V[start]++;
	q.push(start);
	while (!q.empty())
	{
		x = q.front();
		q.pop();
		for (auto& y : a[x])
		{
			if (V[y] == times) continue;
			arr[y] = arr[x] + 1;
			V[y]++;
			q.push(y);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> TE >> FE >> S >> T >> F >> N >> M;
	TFE = TE + FE - S;
	for (int i = 0; i < M; i++)
	{
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	bfs(N, 1, RN);
	if (!V[T] || !V[F])
	{
		cout << -1; return 0;
	}

	bfs(T, 2, RT);
	bfs(F, 3, RF);
	for (int i = 1; i <= N; i++)
		if (V[i] == 3)
			ans = min(ans, RT[i] * TE + RF[i] * FE + RN[i] * TFE);
	cout << ans;
	return 0;
}


#elif QUESTIONS == 2 // 2 蛋糕划分

//蛋糕划分：蛋糕大小N*N，每个部分质量不均，共切k刀(横竖均可)，使最重的一块蛋糕的质量最轻是多少。
#include <iostream>   
#include <cstring>
#include <vector>
using namespace std;     //2≤N≤15，1≤K≤2N−2  ，每个位置质量W小于1000        和洛谷P1182  数列分段一样思路
int n, k, fal, max_;//fal是答案出错标记，方便快速结束循环
int a[20][20], sum[20][20], col[20], cnt[20], temp[20];;//col存放竖刀的位置,cnt是横切后每个区间和，temp是新一列区间和
int get_sum(int x1, int y1, int x2, int y2) {//求上下左右区间和
	return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}
bool check(int m) {
	if (m < max_)return false;//特判
	//第一个循环是对每种横刀状态进行遍历（每一个i都代表一种横刀状态）
	for (int i = 0; i < (1 << (n - 1)); i++) {
		fal = 0;//更新此种横刀状态为正确，内部循环发现是因横刀出错时就一头冲出来
		memset(col, 0, sizeof(col));
		memset(cnt, 0, sizeof(cnt));
		memset(temp, 0, sizeof(temp));
		vector<int> v;
		int count = 0, ans = 0, tmp = i;
		while (tmp) {
			count++;
			if (tmp & 1) {//获取i中1的位置，存入这种状态下的每个横刀位置
				v.push_back(count);//v用来存横刀位置，若v里面为1,3,4，加入n后，表示横刀区间1-1，2-3，4-4，5-n
				ans++;
			}
			tmp /= 2;
		}
		if (ans > k)continue;//特判
		v.push_back(n);
		int p = 0, top = 1, down;//top是该区间最上面元素位置,down是此横刀位置,p为当前的第几个横刀区间（
		//第二个循环是切竖刀的，在每个竖位置遍历列区间，一旦某个横刀区间加上这个列超过答案就说明可以切竖刀了
		for (int j = 1; j <= n; j++) {
			p = 0, top = 1;//每切一次竖刀就重置一次
			//第三个循环是遍历横刀区间的（我们要自上而下遍历每个区间）
			for (int x : v) {//用x来访问v中的所有元素，取出每个横刀位置
				down = x;
				int now = get_sum(top, j, down, j);//求列区间和（列宽为1）
				if (now > m) {//如果仅列区间已经大于答案就说明是横刀状态失误了，fal标记一下，直接冲到最外面
					fal = 1; break;
				}
				//求新的横刀区间（原横刀区间加列区间）
				cnt[++p] += now;//将上个区间加上这个区间
				if (col[j - 1]) {
					cnt[p] = now;//上个位置被切过了，就说明我们不应该加的
				}
				temp[p] = now;//temp存每个列区间和
				//判断该横刀区间，决策是否切竖刀
				if (cnt[p] > m) {//该区间和大于答案，说明要切竖着在j-1的位置一刀，cnt再从第j列开始计算和（你只有犯错的时候才知道自己犯错了）
					col[j - 1] = 1;//更新竖切的位置和区间和
					cnt[p] = now;
					for (int ii = 1; ii < p; ii++)cnt[ii] = temp[ii];//之前的区间也要因此而更新了，用上temp了
				}
				top = down + 1;//top是下个区间最上面位置
			}
			if (fal)break;
		}
		if (fal)continue;
		for (int j = 1; j <= n - 1; j++)
			if (col[j])ans++;//col存放的竖切刀
		if (ans <= k)return true;
	}
	return false;
}
int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)//数据从1，1开始存，后面注意这点
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			max_ = max(max_, a[i][j]);
			sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	int l = 0, r = 2000 * 15 * 15;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (check(m)) r = m - 1;//刀数太少，说明应该再切小一点
		else l = m + 1;
	}
	cout << l << '\n';
	return 0;
}


#elif QUESTIONS == 3 // 3 第五维度

#include<iostream> 

using namespace std;
using ll = long long;
const ll N = 1e6;
ll s[N], v[N], n, m;

bool check(ll t) // 若能理解，返回真
{
	ll sum = 0, maxn = -1;
	for (int i = 1; i <= n; i++) {
		if (t <= s[i]) continue; //当前科学家未到开始时间
		sum += (t - s[i]) * v[i];
		maxn = max(maxn, (t - s[i]) * v[i]);
	}
	return sum - maxn > m;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> s[i] >> v[i];

	ll l = 0, r = 2e9;
	while (l < r) {
		ll mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	if (check(l)) cout << l << endl;
	else cout << -1 << endl;
	return 0;
}


#elif QUESTIONS == 5 // 5 糖果促销

#include<iostream>

using namespace std;

int t, p, k;
int main() {
	cin >> t;
	while (t--) {
		cin >> p >> k;
		if (k == 0) cout << 0 << '\n';//注意题上的数据范围
		else {
			k -= (k - 1) / p;//一个式子就行
			cout << k << '\n';
		}
	}
}

#elif QUESTIONS == 9 // 9 星际航行
#include<iostream> 
#include <algorithm>
using namespace std;

using ll = long long;
const ll maxn = 1e5 + 10;
ll x[maxn], y[maxn], z[maxn];
ll n;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> z[i];
	}
	sort(x, x + n);
	sort(y, y + n);
	sort(z, z + n);
	ll ans = 1e18 + 10;
	ll xmid = x[n / 2], ymid = y[n / 2], zmid = z[n / 2];
	ll tmp = 0;

	// 依次枚举所有点走到中间，且有一维为递增的结果
	for (int i = 0; i < n; i++) {
		tmp += abs(xmid - x[i]);
		tmp += abs(ymid - y[i]);
		tmp += abs(zmid + i - n / 2 - z[i]);
	}
	ans = min(ans, tmp);

	tmp = 0;
	for (int i = 0; i < n; i++) {
		tmp += abs(xmid - x[i]);
		tmp += abs(ymid + i - n / 2 - y[i]);
		tmp += abs(zmid - z[i]);
	}

	ans = min(ans, tmp);

	tmp = 0;
	for (int i = 0; i < n; i++) {
		tmp += abs(xmid + i - n / 2 - x[i]);
		tmp += abs(ymid - y[i]);
		tmp += abs(zmid - z[i]);
	}
	ans = min(ans, tmp);
	cout << ans << endl;

	return 0;
}

#elif QUESTIONS == 10 // 10 小度的规划
#include<iostream> 
#include <vector>

using namespace std;

// 10 小度的规划
/*
* 小度只能走有金币的路 度度熊只能在本节点或相邻节点扔金币
*  小度x之前不关心金币，X->Y捡金币(包括X和Y),走到Y游戏结束，同时要求最短路径 下一步没金币则游戏失败(获得0金币）
* 思路：度度熊先移动到小度的起点，确保小度可以到X，之后沿着预定路线扔金币到Y，贪心把每个节点扔满
*/
// using ll = long long;
const int N = 1501;
int n, fas[N], ans;
int C[N]; // 每个节点容量
int PA, PB; // 小度起点 度度熊起点

vector<int> adj[N];
int dis[N];

// 更新树上节点距离
void dfs1(int u, int fa)
{
	for (auto v : adj[u])
	{
		if (v == fa) continue;
		dis[v] = dis[u] + 1;
		dfs1(v, u);
	}
}

// 度度熊有rest步可以停留 计算在u能扔多少个金币
void dfs3(int u, int fa, int rest, int sum)
{
	if (C[u] == 0)	return;
	//  计算度度熊在节点u停留的最大次数 还有多少个可以扔的 剩余步数
	int t = min(max(C[u] - fas[u], 0), rest);

	// 剩余的步数-停留的次数
	rest -= t;

	// 累加度度熊在当前节点可放置的最大金币数
	sum += t + min(C[u], fas[u]);

	// 更新答案
	ans = max(ans, sum);

	// 度度熊继续向下走
	for (auto v : adj[u])
	{
		if (v == fa) continue;
		fas[v] += 1; // 路过v(v上再丢一个金币)
		dfs3(v, u, rest, sum);
		fas[v] -= 1;
	}

}

// 从PB出发，当前位置在节点u，距PB(度度熊起点)距离为len
void dfs2(int u, int fa, int len)
{
	// 如果度度熊到此处u的距离 <= 小度到此处的距离
	if (len <= dis[u])
		dfs3(u, 0, dis[u] - len, 0);

	for (auto v : adj[u])
	{
		if (v == fa) continue;
		fas[v] += 1;
		dfs2(v, u, len + 1);
		fas[v] -= 1;
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 1; i <= n; i++)
		cin >> C[i];

	cin >> PA >> PB;

	dfs1(PA, 0); // 以小度的起点为根节点，更新树上每个节点的距离
	dfs2(PB, 0, 0);

	cout << ans << endl;
	return 0;
}

#endif // QUESTIONS == ?